#include "DoubleLinkedListWithHead.h"
#include <stdio.h>
#include <stdlib.h>
/*
	Create_Empty_DoubleLinkedListWithHead:创建一条空的双向链表
*/
struct Head*Create_Empty_DoubleLinkedListWithHead()
{
    struct Head*h = malloc(sizeof(struct Head));
    if(h == NULL)
        return h;
    h->num = 0;
    h->first = h->last = NULL;

    return h;
}
/*
	Create_Input_DoubleLinkedListWithHead:从键盘上输入数据创建一条整型数据双向链表
*/
struct Head*Create_Input_DoubleLinkedListWithHead()
{
    //创建一条空链表
    struct Head*h = Create_Empty_DoubleLinkedListWithHead();
    if(h == NULL)
        return h;
    
    while(1)
    {
        int d;
        scanf("%d", &d);
        if(d == 0)
            break;
        //创建新数据节点并赋值
        struct Node*pnew = malloc(sizeof(*pnew));
        if(pnew == NULL)
            return h;
        pnew->data = d;
        pnew->next = pnew->pre = NULL;

        //增加
        if(h->first == NULL && h->last == NULL && h->num == 0)
        {
            h->first = h->last = pnew;
        }
        else
        {
            //pnew->next = NULL;
            pnew->pre = h->last;
            h->last->next = pnew;
            h->last = pnew;
        }
        h->num++;
    }


    return h;
}
/*
	Print_DoubleLinkedListWithHead:输出一条带头结点的整型双向链表
	@h:要输出的链表的头节点指针
	
	返回值：
		无
*/
void Print_DoubleLinkedListWithHead(struct Head*h)
{
    if(h == NULL)
    {
        return ;
    }
    printf("=========================\n");
    if(h->first == NULL && h->last == NULL && h->num == 0)//空链表
    {
        printf("num:%d\n", h->num);
    }
    else
    {
        printf("first->data:%d last->data:%d num:%d\n", h->first->data,h->last->data,h->num);
    }

    printf("Next:");
    struct Node*p = h->first;
    while(p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");

    printf("Pre:");
    p = h->last;
    while(p)
    {
        printf("%d ", p->data);
        p = p->pre;
    }
    printf("\n");
}
/*
	Insert_node_y：在head指向的链表中，找到值为x的节点，在其前面增加一个值为y的节点
*/
void Insert_node_y(struct Head*h, ElemType x, ElemType y)
{
    //1.创建新节点并赋值
    struct Node*pnew = malloc(sizeof(*pnew));
    if(pnew == NULL)
        return ;
    pnew->data = y;
    pnew->next = pnew->pre = NULL;
    if(h->first == NULL && h->last == NULL && h->num == 0)//空链表
    {
        h->first = h->last = pnew;
        h->num++;
        return;
    }
    //2.增加
    //2.1查找
    struct Node*p = h->first;
    while(p)
    {
        if(p->data == x)
            break;
        p = p->next;
    }
    if(p)
    {
        if(p == h->first)
        {
            pnew->next = h->first;
            h->first->pre = pnew;
            h->first = pnew;
        }
        else
        {
            pnew->next = p;
            pnew->pre = p->pre;
            p->pre = pnew;
            pnew->pre->next = pnew;
        }
    }
    else
    {
        pnew->pre = h->last;
        h->last->next = pnew;
        h->last = pnew;
    }
    h->num++;

}
/*
	Delete_all_x:在head指向的带头结点的双向链表中，找到值为x的节点,将其删除
如果有多个值为x的节点则全部删除
	如果没有则不删除
	@head:
	@x:
	@y:
	
	返回值：
		无
*/
void Delete_all_x(struct Head*h, ElemType x)
{
    //先查找再删除
    struct Node*p = h->first;
    while(p)
    {
        while(p)
        {
            if(p->data == x)
                break;
            p = p->next;
        }
        if(p)
        {
            //删除操作
            if(p == h->first)
            {
                h->first = p->next;
                if(h->first)
                    h->first->pre = NULL;
                else
                    h->last = NULL;
                p->next = NULL;
                free(p);
                p = h->first;
            }
            else if(p == h->last)
            {
                h->last = p->pre;
                h->last->next = NULL;
                p->pre = NULL;
                free(p);
                p = NULL;
            }
            else
            {
                struct Node*p_next = p->next;
                p->pre->next = p->next;
                p->next->pre = p->pre;
                p->next = NULL;
                p->pre = NULL;
                free(p);
                p = p_next;
            }
            h->num--;
        }
    }
}